#include<string>
#include<vector>
#include<array>
#include<unordered_map>
#include<algorithm>
#include<limits>
#include <stack>
#include<iostream>
#include<sstream>
#include<deque>
#include<queue>
#include<set>
#include<unordered_set>
#define MOD 1000000007
class Solution {
public:
    int findCheapestPrice(int n, std::vector<std::vector<int>>& flights, int src, int dst, int k) {
        std::vector<int> cur(n,std::numeric_limits<int>::max());
        std::vector<int>next(n,std::numeric_limits<int>::max());
        cur[src] = 0;
        int len = flights.size();
        k++;
      while (k--)
      {
          next.assign(cur.begin(),cur.end());
          for (int i = 0; i < len; i++)
          {
              int start = flights[i][0];
              int end = flights[i][1];
              int weight= flights[i][2];
              if (cur[start]==std::numeric_limits<int>::max()) continue;
              if (next[end] > cur[start] + weight)
              {
                  next[end] = cur[start] + weight;
              }
          }
          cur = next;
      }
        if (cur[dst]==std::numeric_limits<int>::max())
        {
            return -1;
        }
        return cur[dst];
        
    }
};
/*int main()
{
    std::vector<std::vector<int>> flights = {{1,0,5},{2,1,5},{3,0,2},{1,3,2},{4,1,1},{2,4,1}};
    Solution s;
    s.findCheapestPrice(5,flights, 2, 0, 2);
}*/